package leetcode.stack;

import java.util.Stack;

/**
 * DESCRIPTION: https://leetcode-cn.com/problems/score-of-parentheses/
 * 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
 * () 得 1 分。
 * AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 * (A) 得 2 * A 分，其中 A 是平衡括号字符串。
 * Author: ammar
 * Date:   2021/12/16
 * Time:   上午8:12
 */
public class _856_括号的分数 {
    public static void main(String[] args) {
//        String s = "()";
//        System.out.println(scoreOfParentheses(s));
//        String s1 = "(())";
//        System.out.println(scoreOfParentheses(s1));
//        String s2 = "(()(()))";
//        System.out.println(scoreOfParentheses(s2));
        String s3 = "(())()";
        System.out.println(scoreOfParentheses(s3));
    }

    /**
     * 思路：将所有的 ( 入栈，在上一个字符为 ( 时，下一个字符为 ) 计算分数
     * 分数为 2 的 (size - 1) 次方
     * 在求次方运算中，如果底数为2，则可以通过位移来计算 2 的 n 次幂
     * 4 的 2次方，先把4转化为2的2次方，然后 2 << (4 - 1)
     * 2 的 3次方，2 << (3 - 1)
     *
     * @param s
     * @return
     */
    public static int scoreOfParentheses(String s) {
        int score = 0;
        if (s == null || s.equals("")) return score;
        Stack<String> stack = new Stack<>();
        char[] chars = s.toCharArray();
        String last = null;
        for (char aChar : chars) {
            String str = String.valueOf(aChar); // ()
            if ("(".equals(str)) {
                stack.push(str);
            } else {
                stack.pop();
                if (last != null && last.equals("(") && ")".equals(str)) {
                    if (stack.size() == 0) {
                        score = score + 1;
                    } else {
                        score = score + (2 << (stack.size() - 1));
                    }
                }
            }
            last = str;
        }
        return score;
    }
}
